package com.zs.letcode.illustration_of_algorithm;

/**
 * 剑指 Offer 51. 数组中的逆序对
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * 输入: [7,5,6,4]
 * 输出: 5
 * <p>
 * 限制：
 * <p>
 * 0 <= 数组长度 <= 50000
 * <p>
 * 相关标签
 * 树状数组
 * 线段树
 * 数组
 * 二分查找
 * 分治
 * 有序集合
 * 归并排序
 * <p>
 * Java
 * <p>
 * <p>
 * <p>
 * 作者：Krahets
 * 链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/o58jfs/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/8/23 09:12
 */
public class Chapter44 {
    public static void main(String[] args) {

    }

    private class Solution {
        int[] nums, tmp;

        public int reversePairs(int[] nums) {
            this.nums = nums;
            tmp = new int[nums.length];
            return mergeSort(0, nums.length - 1);
        }

        private int mergeSort(int l, int r) {
            // 终止条件
            if (l >= r) {
                return 0;
            }
            // 递归划分
            int m = (l + r) / 2;
            int res = mergeSort(l, m) + mergeSort(m + 1, r);
            // 合并阶段
            int i = l, j = m + 1;
//            for (int k = l; k <= r; k++) {
//                tmp[k] = nums[k];
//            }
            if (r + 1 - l >= 0) System.arraycopy(nums, l, tmp, l, r + 1 - l);
            for (int k = l; k <= r; k++) {
                if (i == m + 1) {
                    nums[k] = tmp[j++];
                } else if (j == r + 1 || tmp[i] <= tmp[j]) {
                    nums[k] = tmp[i++];
                } else {
                    nums[k] = tmp[j++];
                    res += m - i + 1;
                }
            }
            return res;
        }
    }
}
